package 剑指Offer专项突破;

import test0ne.TreeNode;

import java.util.*;

/**
 * @Author zhang lei
 * @Date 2022-04-24 21:10
 * 树的遍历
 */
public class Tree {
//    public static void main(String[] args) {
//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(2);
//        root.right = new TreeNode(3);
//
//        root.left.left = new TreeNode(4);
//        root.left.right = new TreeNode(5);
//
//        root.right.left = new TreeNode(6);
//        root.right.right = new TreeNode(7);
//
//        System.out.println(sumNumbers(root));
////        pruneTree(root);
////        System.out.println();
//
////        System.out.println("先序遍历: preOrder");
////        preOrder(root);
////        System.out.println();
////        preOrderIter(root);
////
////        System.out.println("\n中序遍历：inOrder");
////        inOrder(root);
////        System.out.println();
////        inOrderIter(root);
////
////        System.out.println("\n后续遍历：postOrder");
////        postOrder(root);
////        postOrder2(root);
////        String s = null;
////        System.out.println(s = serialize(root));
////        TreeNode root1 = deserialize(s);
////        System.out.println();
//
//    }

    private static void preOrder(TreeNode root) {
        if(root != null) {
            System.out.print(root.val);
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    /**
     * 迭代 先序
     * @param root
     */
    private static void preOrderIter(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur!= null || !stack.isEmpty()) {
            while (cur != null) {
                System.out.print(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode pop = stack.pop();
            cur = pop.right;
        }
    }

    /**
     * 迭代 中序
     * @param root
     */
    private static void inOrder(TreeNode root) {
        if(root != null) {
            inOrder(root.left);
            System.out.print(root.val);
            inOrder(root.right);
        }
    }

    private static void inOrderIter(TreeNode root) {
        Stack<TreeNode> s = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !s.isEmpty()) {
            while (cur != null) {
                s.push(cur);
                cur = cur.left;
            }
            TreeNode pop = s.pop();
            System.out.print(pop.val);
            cur = pop.right;
        }
    }

    /**
     * 迭代 后序
     * @param root
     */
    private static void postOrder(TreeNode root) {
        if(root != null) {
            preOrder(root.left);
            preOrder(root.right);
            System.out.print(root.val);
        }
    }

    /**
     * 1、先一直左侧深度遍历
     * 2、每次peek栈顶，判断是否有右侧节点
     * 3、写了次，还是有bug， 问题是记录当前的前一个节点 pre，等再次到栈顶的时候，判断pre节点是否等于栈顶的又节点
     * @param root
     */
    private static void postOrder2(TreeNode root) {
        Stack<TreeNode> s = new Stack<>();
        TreeNode cur = root;

        TreeNode pre = null;
        while (cur != null || !s.isEmpty()) {
            while (cur != null) {
                s.push(cur);
                cur = cur.left;
            }
            cur = s.peek();
            if(cur.right != null && pre != cur.right) {
                cur = cur.right;
            }else {
                cur = s.pop();
                System.out.print(cur.val);
                pre = cur;

                cur = null;
            }
        }
    }

    /**
     * 47题 剪枝
     * @param root
     * @Desc 思路：划重点，这个题拿到后，想想后序遍历，左边处理后，右边处理后，如果都是null了，那么判断当前节点值是否为0，如果都满足返回null
     * 碰见二叉树的问题， 先想想用哪种遍历， 逻辑部分组织下就行
     * @return
     */
    private static TreeNode pruneTree(TreeNode root) {
        if(root == null) {
            return null;
        }

        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if(root.left == null && root.right == null && root.val == 0) {
            return null;
        }
        return root;
    }


    // Encodes a tree to a single string.
    private static final String sep = "#";

    private static final StringBuilder sb = new StringBuilder();

    /**
     * 层序遍历序列化，反序列化简单
     * @param root
     * @return
     */
    public static String serialize(TreeNode root) {
        if(root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        LinkedList<TreeNode> list = new LinkedList<>();
        list.push(root);
        while (!list.isEmpty()) {
            int num = list.size();
            for (int i = 0; i < num; i++) {
                TreeNode peek = list.poll();
                if(peek != null) {
                    sb.append(peek.val).append(",");
                    list.add(peek.left);
                    list.add(peek.right);
                }else {
                    sb.append(sep).append(",");
                }
            }
        }
        return sb.toString().substring(0, sb.length()-1);
    }

    // Decodes your encoded data to tree.
    /**
     * 先写下思路
     * 因为序列化的时候使用的是 层序，所以反序列化也是层序
     * 一个队列，一个数组，index指针
     * @param data
     * @return
     */
    public static TreeNode deserialize(String data) {
        if(data.length() == 0) {
            return null;
        }
        LinkedList<TreeNode> list = new LinkedList<>();
        String[] arr = data.split(",");
        TreeNode root = new TreeNode(Integer.valueOf(arr[0]));
        list.addFirst(root);
        deser(list, arr, 1);

        return root;
    }

    private static void deser(LinkedList<TreeNode> list, String[] arr, int i) {
        while (!list.isEmpty() && i<arr.length) {
            TreeNode cur = list.poll();
            //读后面两个值
            if(cur == null) {
                continue;
            }
            list.addLast( cur.left = getNextTreeNode(arr[i++]));
            if(i<arr.length) {
                list.addLast( cur.right = getNextTreeNode(arr[i++]));
            }
        }
    }

    private static TreeNode getNextTreeNode(String s) {
        return s.equals(sep)? null:new TreeNode(Integer.valueOf(s));
    }


    /**
     * 049 从根节点到叶节点的路径数字之和
     * 左右都没有才算结束
     * 这道题面过，没做出来
     * @param root
     * @return
     */
    public static int sumNumbers(TreeNode root) {
        return recur(root, 0, 0);
    }

    private static int recur(TreeNode root, Integer pre, Integer sum) {
        if(root!=null) {
            if(root.left == null && root.right == null) {
                sum += pre*10 + root.val;
            }else {
                int left = recur(root.left, pre*10+root.val, sum);
                int right = recur(root.right, pre*10+root.val, sum);
                sum = left+right;
            }
        }
        return sum;
    }


    /**
     * 050 向下的路径节点之和
     * @param root
     * @param targetSum
     * @return
     */
    public static int pathSum(TreeNode root, int targetSum) {
        if(root == null) {
            return 0;
        }
        return compute(root, targetSum);
    }

    private static int compute(TreeNode root, int targetSum) {
        if(root == null) {
            return 0;
        }
//        System.out.println("遍历以 主节点:"+root.val+ "左节点:"+root.left.val);
        return computeChild(root, targetSum) + compute(root.left, targetSum) + compute(root.right, targetSum);
    }

    private static int computeChild(TreeNode root, int targetSum) {
        if(root == null) {
            return 0;
        }
        if(targetSum - root.val == 0) {
            if(root.left == null && root.right == null) {
                return 1;
            }else {
                return 1 + computeChild(root.left, targetSum-root.val) + computeChild(root.right, targetSum-root.val);
            }
        }
        return computeChild(root.left, targetSum-root.val) + computeChild(root.right, targetSum-root.val);
    }

    public static TreeNode increasingBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode first = null;
        TreeNode pre = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode pop = stack.pop();
            pop.left = null;
            if(pre != null) {
                pre.right = pop;
            }
            pre = pop;
            if(first == null) {
                first = pop;
            }
            cur = pop.right;
        }
        return first;
    }

    /**
     * 053 二叉搜索树中的中序后继
     * @param root
     * @param p
     * @return
     */
    private static TreeNode next = null;

    public static TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
         inorderSuccessor2(root, p);
         return next;
    }

    private static void inorderSuccessor2(TreeNode root, TreeNode p) {
        if (root != null) {
            if(root.val <= p.val) {
                //中序遍历右节点，找到大于p.val的最小值
                inOrder2(root.right, p);
            }else {
                //左节点
                next = root;
                inOrder2(root.left, p);
            }
        }
    }

    private static void inOrder2(TreeNode root, TreeNode p) {
        if(root == null) {
            return;
        }
        inOrder2(root.left, p);
        if(root.val> p.val) {
            next = next == null? root: (next.val<root.val? next: root);
        }
        inOrder2(root.right, p);
    }

    /**
     * 054 所有大于或等于节点的值之和
     * @param root
     * @return
     */
    public static TreeNode convertBST(TreeNode root) {
        if(root == null) {
            return null;
        }

        LinkedList<Integer> list = new LinkedList<>();
        convertBSTPost(root, list);
        convertBSTPost2(root, list);

        return root;
    }

    private static void convertBSTPost2(TreeNode root, LinkedList<Integer> list) {
        if(root == null) {
            return;
        }

        convertBSTPost2(root.right, list);
        root.val = list.poll();
        convertBSTPost2(root.left, list);
    }

    private static void convertBSTPost(TreeNode root, LinkedList<Integer> list) {
        if(root == null) {
            return;
        }
        convertBSTPost(root.right, list);
        if (list.size() == 0) {
            list.add(root.val);
        } else {
            list.add(list.getLast() + root.val);
        }
        convertBSTPost(root.left, list);
    }




    /**
     * 056
     * @param root
     * @param k
     * @return
     */
    public static boolean findTarget(TreeNode root, int k) {
        if(root == null) {return false;}
        Map<Integer, Integer> map = new HashMap<>();

        return justFindTarget(root, k, map);
    }

    private static boolean justFindTarget(TreeNode root, int k, Map<Integer, Integer> map) {
        if(root != null) {
            boolean left = justFindTarget(root.left, k, map);
            boolean right = justFindTarget(root.right, k, map);
            boolean flag = false;
            if(map.get(k-root.val) != null)  {
                flag = true;
            }

            return  flag || left || right;
        }
        return false;
    }


    public static void main(String[] args) {
        TreeNode root = TreeNode.buildTreeNode(new Integer[]{4,1,6,0,2,5,7,null,null,null,3,null,null,null,8});
        TreeNode.printTreeNode(convertBST(root));
    }
}
